import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MaxHeap<T extends Comparable<T>> {
    private List<T> data = new ArrayList<>();

    //获得父亲的索引
    private int parent(int now) {
        return (now - 1) / 2;
    }

    //获取左孩子索引
    private int leftChild(int now) {
        return (now * 2) + 1;
    }

    //获取右孩子索引
    private int rightChild(int now) {
        return (now * 2) + 2;
    }

    // 对now索引位置元素进行sift Up操作
    public void siftUp(int now) {
        while (now > 0 && data.get(now).compareTo(data.get(parent(now))) > 0) {//子节点比父节点大了，违反规则
            //交换父子
            T tem = data.get(now);
            data.set(now, data.get(parent(now)));
            data.set(parent(now), tem);

            now = parent(now);
        }
    }

    public void add(T e) {
        data.add(e);
        siftUp(data.size() - 1);
    }

    private T findMax(){
        if (data.size() == 0)
            throw new IllegalArgumentException("堆已经空");
        return data.get(0);
    }
    //把堆顶元素移出，并返回
    public T extractMax() {
        T ret = findMax();
        //把最后一个元素放到第一个元素位置
        data.set(0, data.get(data.size() - 1));
        //删除最后一个元素
        data.remove(data.size() - 1);

        siftDown(0);
        return ret;
    }

    public void siftDown(int now) {

        while (leftChild(now) < data.size() ) {//左孩子越界时，右孩子一定也越界了
            T max = data.get(now);//当前节点，左右孩子中最大的节点
            //一定有左孩子

            int j = leftChild(now);//j 是左右孩子中较大的那一个的索引

            if (rightChild(now) < data.size() && //有右孩子
            data.get(rightChild(now)).compareTo(data.get(leftChild(now))) > 0) {//且右孩子比左孩子大
                j = rightChild(now);
            }

            if (data.get(now).compareTo(data.get(j)) < 0) {
                //左右孩子中的最大值，要比根节点还大。大值上浮
                T tem = data.get(j);
                data.set(j, data.get(now));
                data.set(now, tem);
            }

            now = j;
        }
    }

    //把arr heapify成最大堆
    public void heapify(T[] arr) {
        data = new ArrayList<T>(Arrays.asList(arr));//把以前有的数据干掉

        int k = parent(arr.length - 1);//找出最后一个非叶子节点。（最后一个节点的父节点就是最后一个非叶子节点）

        //heapify
        for (int i = k; i >= 0 ; i--) {
            siftDown(i);
        }
    }


    public static void main(String[] args) {
        MaxHeap<Integer> maxHeap = new MaxHeap<>();
        /*maxHeap.add(3);
        maxHeap.add(4);
        maxHeap.add(1);
        maxHeap.add(8);
        System.out.println(maxHeap.extractMax());
        System.out.println();*/

        Integer[] arr = {3, 4, 1, 8, 5, 9};
        maxHeap.heapify(arr);
        System.out.println();

    }
}
